//q7.cpp
//This program implement proper group functions
//
//Binyamin 27 Jan 2018
//-----------------------------------------------

#include<iostream>

using namespace std;

//intersect
//input: two arrays and their size
//output: an array which hold the values that were stored in both arrays.
//runtime: size_a OR size_b, whichever is smaller.
int *intersect(int *a, int size_a, int *b, int size_b, int *size_aintb)
{
	int index_a, index_b;
	int count;
	int *ret;
	if(size_a>= size_b)
		ret = new int[size_b];
	else ret = new int[size_a];
	index_a = 0;
	index_b = 0;
	count = 0;
	while((index_a < size_a) && (index_b < size_b))
	{
		if(a[index_a] == b[index_b])
		{
			ret[count] = b[index_b];
			count++;
			index_a++;
			index_b++;
		}
		else if(a[index_a] < b[index_b]) 
		{
			index_a++;
		}
		else index_b++;
	}
	*size_aintb = count;
	return ret;
}

//unite
//input: two arrays and their size.
//output: array holding both arrays memebers together.
//runtime: size_a + size_b
int *unite(int *a, int size_a, int *b, int size_b, int *size_aintb)
{
	int index_a, index_b;
	int count;
	int *ret;
	ret = new int[size_a+size_b];
	index_a = 0;
	index_b = 0;
	count = 0;
	while((index_a < size_a) && (index_b < size_b))
	{
		if(a[index_a] == b[index_b])
		{
			ret[count] = a[index_a];
			count++;
			index_a++;
			index_b++;
		}
		else if(a[index_a] < b[index_b]) 
		{
			ret[count] = a[index_a];
			index_a++;
			count++;
		}
		else 
		{
			ret[count] = b[index_b];
			index_b++;
			count++;
		}
	}
	for(;index_a<size_a;index_a++, count++)
		ret[count] = a[index_a];
	for(;index_b<size_b;index_b++, count++)
		ret[count] = b[index_b];

	*size_aintb = count;
	return ret;
}

//minuss
//input: two arrays and their size.
//output: an array with the members of the first which are NOT in the second
//runtime: size_a
int *minuss(int *a, int size_a, int *b, int size_b, int *size_aintb)
{
	int index_a, index_b;
	int count;
	int *ret;
	ret = new int[size_a];
	index_a = 0;
	index_b = 0;
	count = 0;
	while((index_a < size_a) && (index_b < size_b))
	{
		if(a[index_a] == b[index_b])
		{
			index_a++;
			index_b++;
		}
		else if(a[index_a] < b[index_b]) 
		{
			ret[count] = a[index_a];
			index_a++;
			count++;
		}
		else 
		{
			//ret[count] = b[index_b];
			index_b++;
			//count++;
		}
	}
	for(;index_a<size_a;index_a++, count++)
		ret[count] = a[index_a];
	//for(;index_b<size_b;index_b++, count++)
	//	ret[count] = b[index_b];

	*size_aintb = count;
	return ret;
}
//xorr
//input: two arrays and their size
//output: the members which are just once in the arrays.
//runtime: size_a + size_b
int *xorr(int *a, int size_a, int *b, int size_b, int *size_axorb)
{
	int *anb;
	int *aub;
	int *aib;
	int size_anb, size_aub, size_aib;
	anb = intersect(a, size_a, b, size_b, &size_anb);
	aub = unite(a, size_a, b, size_b, &size_aub);
	aib = minuss(aub, size_aub, anb, size_anb, &size_aib);
	*size_axorb = size_aib;
	return aib;
}

const int SIZE = 5;
//1. generate test arrays.
//2. run intersect and print the result
//2. run unite and print the result
//2. run minuss and print the result
//2. run xorr and print the result
int main()
{
	int b[] = {1, 2, 3, 4, 5};
	int a[] = {3, 4, 5, 6, 7};
	int sizeab;
	int *ab;
	ab = intersect(a, SIZE, b, SIZE, &sizeab);
	for(int i=0;i<sizeab;i++)
		cout << ab[i] << '\t';
	cout << endl;
	ab = unite(a, SIZE, b, SIZE, &sizeab);
	for(int i=0;i<sizeab;i++)
		cout << ab[i] << '\t';
	cout << endl;
	ab = minuss(a, SIZE, b, SIZE, &sizeab);
	for(int i=0;i<sizeab;i++)
		cout << ab[i] << '\t';
	cout << endl;
	ab = xorr(a, SIZE, b, SIZE, &sizeab);
	for(int i=0;i<sizeab;i++)
		cout << ab[i] << '\t';
	cout << endl;
}
//output
//3	4	5	
//1	2	3	4	5	6	7	
//6	7	
//1	2	6	7	
